package array.prefixsum;

import java.util.ArrayList;

public class ProductOfNumbers {

    // 前缀积数组
    // preProduct[] / preProduct[j] 就是 [i ... j]之间的积
    ArrayList<Integer> preProduct = new ArrayList<>();

    ProductOfNumbers() {
        // 初始化放个1， 便于后续添加元素的乘积
        preProduct.add(1);
    }

    public void add(int number) {
        if (number == 0) {
            // 如若添加的是0，则后面的元素积都废了
            preProduct.clear();
            preProduct.add(1);
            return;
        }

        int n = preProduct.size();
        // 前缀积中每个元素
        preProduct.add(preProduct.get(n - 1) * number);

    }

    public int getProduct(int k) {
        int n = preProduct.size();
        if (k > n - 1)
            // 不足 k 个元素，是因为最后 k 个元素存在0
            return 0;
        // 计算最后 k 个元素的前缀积
        return preProduct.get(n - 1) / preProduct.get(n - 1 - k);
    }
}
